//
// Created by 刘振舟 on 2024/3/18.
//
#include <stdlib.h>
#include <stdio.h>
#include <uthash.h>

 struct TreeNode {
     int val;
     struct TreeNode *left;
     struct TreeNode *right;
 };

struct TreeNode* createTreeNode(int val) {
    struct TreeNode *node = (struct TreeNode *) malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

struct QueueNode {
    struct TreeNode *node;
    struct QueueNode *next;
};

struct Queue {
    struct QueueNode *front;
    struct QueueNode *rear;
    int size;
};

struct Queue *initQueue() {
    struct Queue * queue = (struct Queue *) malloc(sizeof(struct Queue));
    queue->front = NULL;
    queue->rear = NULL;
    queue->size = 0;
    return queue;
}

void enqueue(struct Queue *queue, struct TreeNode *node) {
    struct QueueNode *newNode = (struct QueueNode *) malloc(sizeof(struct QueueNode));
    newNode->next = NULL;
    newNode->node =node;
    if (queue->size > 0) {
        queue->rear->next = newNode;
    } else{
        queue->front = newNode;
    }
    queue->rear = newNode;
    queue->size++;
}

struct TreeNode *dequeue(struct Queue *queue) {
    if (queue->size == 0) {
        return NULL;
    }
    struct TreeNode *treeNode = queue->front->node;
    struct QueueNode *temp = queue->front;
    queue->front = queue->front->next;
    free(temp);
    queue->size--;
    if (queue->size == 0) {
        queue->rear = NULL;
    }
    return treeNode;
}


int minDepth(struct TreeNode* root){
    if (!root) {
        return 0;
    }
    int depth = 1;
    struct Queue *queue = initQueue();
    enqueue(queue, root);
    while (queue->size > 0) {
        int size = queue->size;
        for (int i = 0; i < size; ++i) {
            struct TreeNode *node = dequeue(queue);
            if (node->left) {
                enqueue(queue, node->left);
            }
            if (node->right) {
                enqueue(queue, node->right);
            }
            if (!node->left && !node->right) {
                return depth;
            }
        }
        ++depth;
    }
    return depth;
}

struct HashTable {
    char str[5];
    UT_hash_handle hh;
};

struct Node {
    char str[5];
    int val;
};

char num_prev(char x) {
    return x == '0' ? '9' : x - 1;
}

char num_succ(char x) {
    return x == '9' ? '0' : x + 1;
}

char** getNextStatus(char* status, int* retSize) {
    char **ret = malloc(sizeof(char *) * 8);
    *retSize = 0;
    for (int i = 0; i < 4; ++i) {
        char num = status[i];
        status[i] = num_prev(num);
        ret[(*retSize)] = malloc(sizeof(char) * 5);
        strcpy(ret[(*retSize)++], status);
        status[i] = num_succ(num);
        ret[(*retSize)] = malloc(sizeof(char) * 5);
        strcpy(ret[(*retSize)++], status);
        status[i] = num;
    }
    return ret;
}

int openLock(char** deadends, int deadendsSize, char* target) {
    char str_initial[5] = "0000";
    if (strcmp(target, str_initial) == 0) {
        return 0;
    }
    struct HashTable* dead = NULL;
    struct  HashTable* temp;
    for (int i = 0; i < deadendsSize; ++i) {
        HASH_FIND(hh, dead, deadends[i], sizeof(char) * 5, temp);
        if (temp == NULL) {
            temp = malloc(sizeof(struct HashTable));
            strcpy(temp->str, deadends[i]);
            HASH_ADD(hh, dead, str, sizeof(char) * 5, temp);
        }
    }
    HASH_FIND(hh, dead, str_initial, sizeof(char) * 5, temp);
    if (temp != NULL)
        return -1;
    struct Node queue[10001];
    int left = 0, right = 0;
    strcpy(queue[right].str, str_initial);
    queue[right++].val = 0;

    struct HashTable* seen = NULL;
    temp = malloc(sizeof( struct HashTable));
    strcpy(temp->str, str_initial);
    HASH_ADD(hh, seen, str, sizeof(char ) * 5, temp);

    while (left < right) {
        char* status = queue[left].str;
        int step = queue[left++].val;
        int nextStatusSize;
        char **nextStatus = getNextStatus(status, &nextStatusSize);

        for (int i = 0; i < nextStatusSize; ++i) {
            struct HashTable *tmp1, *tmp2;
            HASH_FIND(hh, dead, nextStatus[i], sizeof(char ) * 5, tmp1);
            HASH_FIND(hh, seen, nextStatus[i], sizeof(char ) * 5, tmp2);
            if (tmp1 == NULL && tmp2 == NULL) {
                if (strcmp(nextStatus[i], target) == 0) {
                    return step + 1;
                }
                strcpy(queue[right].str, nextStatus[i]);
                queue[right++].val  = step + 1;
                temp = malloc(sizeof(struct HashTable));
                strcpy(temp->str, nextStatus[i]);
                HASH_ADD(hh, seen, str, sizeof(char) * 5, temp);
            }
        }
    }
    return -1;
}



int main() {
    struct TreeNode *root = createTreeNode(3);
    root->left = createTreeNode(9);
    root->right = createTreeNode(20);
    root->right->left = createTreeNode(15);
    root->right->right = createTreeNode(7);

    printf("The Minimum depth of a tree is: %d", minDepth(root));

    return 0;
}